package com.dbh.alg.algorithm.recursion;

/**
 * 递归插入排序
 *
 * @author 董帮辉
 * @date 2025/4/19
 **/
public class E05InsertionSort {

    public static void sort(int[] arr) {
        insertion(arr, 1);
    }

    private static void insertion(int[] arr, int low) {
        if (low == arr.length) {
            return;
        }

        int t = arr[low];
        int i = low - 1;
        while (i >= 0 && arr[i] > t) {  // 没找到待插入位置
            arr[i+1] = arr[i];  //将i位置空出来
            i--;
        }

        // 找到插入位置
        if (i + 1 != low) {
            arr[i + 1] = t;
        }

        insertion(arr, low + 1);
    }
}
